package com.zxy.javaarithmetic.chapter_1_StackQueue;

import java.util.Deque;
import java.util.LinkedList;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_1_StackQueue
 *  @文件名:   P_7_MaxWindowArr
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/3 11:34
 *  @描述：    生成窗口的最大值数组，时间复杂度O(n),n为原始数组长度
 */
public class P_7_MaxWindowArr {

	public static void main(String[] args){
		int[] data = {4,3,5,4,3,3,6,7};
		int[] maxWindows = getMaxWindow(data,3);
		for (int temp : maxWindows) {
			System.out.print(" "+temp);
		}
	}

	public static int[] getMaxWindow(int[] arr, int w) {
		if (arr == null || arr.length == 0) {
			return new int[0];
		}

		int[] result = new int[arr.length - w + 1];
		int index = 0;

		//用一个双向队列依次存放
		Deque<Integer> deque = new LinkedList<>();
		for (int i = 0; i < arr.length; i++) {
			while (!deque.isEmpty() && arr[deque.peekLast()] <= arr[i]) {
				deque.pollLast();
			}
			deque.addLast(i);

			//删除队列头过期的元素
			if (deque.peekLast() - w == deque.peekFirst()) {
				System.out.println("pollFirst=" + arr[deque.pollFirst()]);
			}
			if (i >= w - 1) {
				result[index++] = arr[deque.peekFirst()];
			}
		}

		return result;
	}
}
